(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "mit :: lcs :: tm :: MIT-LCS-TM-019"

m 



UMULASiJLElED 



Security Classification 



DOCUMENT CONTROL DATA - R&D 



(Security classification of title, body of abstract and in de xing annotation must be entered when the overall report is classified) 

1. ORIGINATING ACTIVITY (Corporate author) 

Massachusetts Institute of Technology 

Project MAC None 



2a. REPORT SECURITY CLASSIFICATION 

UNCLASSIFIED 



2b. GROUP 



3. REPORT TITLE 



A New List-Tracing Algorithm 



4. DESCRIPTIVE NOTES (Type of report and inclusive dates) 

Techn ical Memorandum 



5. AUTHOR(S) (Last name, first name, initial) 

Fenichel , Robert R. 



6. REPORT DATE 

October 1970 



8a. CONTRACT OR GRANT NO. 

Nonr-4102(01) 

ft. PROJECT NO. 



la. TOTAL NO. OF PAGES 

26 



7b. NO. OF REFS 

13 



9«. ORIGINATOR'S REPORT NUMBER(S) 

MAC TM-19 



9b. OTHER REPORT NO(S) (Any other numbers that may be 
assigned this report) 



10. AVAILABILITY/LIMITATION NOTICES 



Distribution of this document is unlimited, 



11. SUPPLEMENTARY NOTES 

None 



12. SPONSORING MILITARY ACTIVITY 

Advanced Research Projects Agency 

3D-200 Pentagon 

Washington, D.C. 2Q3Q1 



13. ABSTRACT 



List-processing systems have each allowed use of only a single size and 
configuration of list cell. This paper describes a system which allows 
use of arbitrarily many different sizes and configurations of list cell, 
possibly not specified until run time. 



14. KEY WORDS 



Li st-Processing 



Garbage Col lection 



Storage Al location 



DD/*r.. 1473 (M.IX) 



UNCLASSIFIED 



Security Classification 



ACKNOWLEDGMENT 



Work reported herein was supported in part by 
Project MAC, an M.I.T. research project sponsored 
by the Advanced Research Projects Agency, Department 
of Defense, under Office of Naval Research Contract 
Nonr-4i02(0l). 



A NEW LIST-TRACING ALGORITHM 

MAC Technical Memorandum 19 

Robert R. Fenichel 
October 1970 



PROJECT MAC 
Massachusetts Institute of Technology 

Cambridge Massachusetts 02139 



ABSTRACT 



List-processing systems have each allowed use of only a 
single size and configuration of list cell. This paper describes 
a system wh ich al lows use of arbitrarily nany :i if f e rent si zes and 
configurations of list cell, possibly not specified until run 
time. 



1 . 1 nt roduct ion 

List-processing systems ( e.g. , LISP 1.5 [l'J , SLIP [12] ) 
have each al lowed use of only a s iagl e s i zo and conf i,,u rat ion of 
list cell. (1) This paper describes a system which allows use of 
arbitrarily many different sizes and configurations of 1 ist 
cells, poss i hi y not spec If ied until run t hue . 

i-'ul t i pi e sizes n\-\d conf igu rat ions of list cells a re 
important in nany applications where the natural quanta of data 
are not homogeneous in size and format. For example, an 
a 1 geh ra ic into rprete r m ight reco r\ the fo 1 low inr info mat ion 
about each variable known to it: 



ref c ronce count 

value 

p r in t name 

po inter to hash- tab 1 e ent ry 

The interpreter m ight al so handl e f 1 oat ing-po int nunbe rs as 

objects. Now, if only a single cell-size is allowed, then cither 

floating-point numbers will be represented with extravagant waste 

of space, or variables will each he chained out into several 

7T) The a ho rted LISP 2 systei 1 [l] wa s to have all owe d mu 1 t i d 1 e 
cell sizes and configurations, but only with a bit of "systems 
programming ... beyond the domain of the average user 11 [_b , p. 7 J 
suppo rt ing each type of eel 1 . 



smaller cells, with concomitant waste of boll; space (for spurious 
pointers link inn the cells) and tine (for following the spurious 
po in te rs ) • 

It will appea r (Section 2 below) that 1 ist-t roc in- is the 
primary obstacle to imp! omenta t ion of 1 is t-p rocess in-; systems 
w it h mul t i pi e s i zos and corf i au rat ions of colls. Sect ions 3 an d 
h describe a tecbn ioue f o r 1 i st-t rae in a in such systems . ( 1 ) 

The remainder of the paper is none rally tutorial, relating 
the list-tracer of the earlier sections to existing problems and 
so 1 ut ions in 1 i s t-p rocess i n,: . 

2 . The 1 mpo rtance of L ist Trac i n,r 



Any 1 ist-p rocess i n^ system must provide moans for obtaining 
single list cells from free storage ( n u c e 1 1 ) , for sett in;; and 
exam in in^ the contents of the various f f a 1 ds of a :? iven list cell 
( set / look ) , and fo r rata re \nz d isused list st ructu r~ to f r^e 
sto ra;- e ( e rasel ist ) . Othr r se rv ices a re gene rn 1 1 y def inod i n 
te rns of these p r im i t i ves . ( 2 ) 



( 1 ) Af te r develop in- this tecbn ioue, the nut ho r brca ao awa re of 
the somewhat re 1 a ted wo rk of S . Ma rs^a 1 1 [:■] . 

(2) Here and below, services not related to 1 ist processing are 
i rno red 



For exnnnle, only a small portion 



, c ? I ^ n 



I ZP is r' 1 1 evant ; 



most of LISP is concerned with f i.mct ion-appl icatioo, a r i t hmet i c , 
and o the r e:;t raucous se rv ices. 



2.1 'iuool 1 



Obtaining col 1 s f ror. free 



lo ra '■ 



r 1 at ive 1 y 



wel 1-understood proMo;-, even when col Is of unpro-'-i ictnblo s i zn 
must bo id ivered. [6, p,, a35-U3l] In each t re \\ i io..al 

1 ist-p rocess in-; system, this servicn is ■> rov i J.oc! by a built- in 
f u net ion; (1) in no rio rn, .peno ra 1 -pu rposo pro" ra vi ^ in,-, laupaa-es, 
run- 1 ine rout i nes a re necessa r i 1 y p rov i nod to po rfo rm this 
service, ( 2 ) 

2.2 Set/loo!; 

Sotting and exaninin- the contents of fields within list 
col 1 s has neve r been even a code-oot in i zat ion p roH e i. in each 

traditional 1 is t-arocrss iip syst-n, there '^ re a setting function 
and an nxnninin^ function f o r oach- f io 1 d of the st an da r ■] list 



cell. (3) Acb! in;: a now type of cell to 



add in: 



a Pei/ no re set t i n,p orv J ox a™ ir i 



1 :• ■> * 



ant< 



unet ion s to 



1 ib ra ry . 



( 1 ) EjJls./ cons in LISP a n d nucel 1 in SLIP. 

(2) E . r. . , The routines supnortlnp ALLOCATE statements in PL/ 1 



r the FREE (sic) routine in AEP [ll]. 



w 



(3 ) In L I SP / f o r exnrinl e, the nuribe r of f io lis is two, so the 
system provides two examining functions ( ca r and cdr ) am! two 
setting functions ( rpl aca and rpl acd ) . 



I n systens onheddod w i thin node m ; ; ;cne ra 1 -;ju rposc 1 amojapos , 
these nunc reus bu i 1 I- i n f uj ,ct ions a re not npcessa ry . Us inr 
based- st rue tu re loci a r^ t ions ( 1 ) w i th in such 1 an;-; a a pes , f ie lis of 
a rb itrary list colls nay bo rnfe ranee d by nnanon ic nan^s, and 
accessed by jp-1 ire code. 

2.3 E ra sel i st 

Returning disused 1 ist-structuro to f r 5 e s t o re r e nu s t h c 
performed by sone variation of ohp (or both [l?J) °^ ~' rp 
f o 1 1 ov/ i n ■; two no t hod s : 



2.3.1 Ga rbai-e col 1 cct ion [oj 



When free storape is in short supply (or, as 
in ) h J , when it Is undo si rably scattered), trace 
all 1 ist-structurr access ib 1 c by p rop ran, na rk i np 
all cells touched. Then scan the entire region of 
nerio ry f ron which cells arc taken. Durinr t'ds 
scan, pi ace unr la rked ( = i n access Pile) cells on t K e 



free-storage 1 ist, arr 
via rked eel 1 s . 



re novo 



a a rks f ron 



(1) This terminology is that of PL/1. Users of AED or of SAL [?] 
declare conponent s . 



■7- 



2.3.2 01 <; c a r ' , ! - S c a ri n i n :; 



t=] 



When n piece of 1 i s t-s t rue tti m is di sea Hoi 
by a user program, trace through this structure 
and return ell of the cH 1 s involved in it Lo free 
storage. As a refinement (as in [l^]), allow 
eel 1 s to hoi d rcf e re rice counts, an.! retu rn 
subs t ructu res to free storage only when they are 
no longer shared as subs t rue tu re by non- \i i sea Hod 
st ructu res . 

E i the r of these methods roqu I res a a rocedu re fo r 
tracing through a list structure. (1) Such a procedure- nust 
be able to accept a pointer to a cell C and, usinr this 
po i n t e r , to e x p 1 o re C^_ i J e n t if y inn all of the other cells 
wh ich have C as 1 ist-pa rent . The p rocedu re must riot be 
misled by the presence in C of irrelevant fields containing 
float inr^-po int nunbe rs, f 1 a;:-b it s, o r othe r non-ad :i resses . 



The 1 i s t - 1 ra c i n n; o ro e e d u ro is the only essential 
1 is t-p races s i ng so rv i ce wh ich is not rout He 1 y p rov idea by 

(1) The o ri,: inal SLIP impl cmen t a t i o r; [l iTj s p r e a i s t \ - e t r a c e 
out thinly and d i scant iruraous 1 y in tine. This is in 

pi eas ing a ceo rdance wi th the ear iaoe ring p r inc ipl e wh ioh 
f avo rs smooth, cont inua 1 appl icat ion of ene rr>y . The tota 1 
ef fo rt i s the same, howeve r, and the info mat ion needed by 
the p ro c e d u re is unc h a n ;; o d . 



node rn >;ene ra 1 -pu rposc I an,-iiu;;es , 



3 . Po inters and T v o c 1 nf o rrnat ion 



Even though each L ran it iona 1 1 i s 1: - p rocoss in;:; i,y s ten 
allows only a single s i ze of cell/ none sots by with only a 
s incl c type of coll. In L ! 3d, f o r e;;nnel e, tho re a re :;tons 
arid non-atons, In SLIP, there arc headc rs on! non-hea 'Inrs. 



G i ven a ;.)o into r to a cell C., the type of £ must he 
computable. ' n early inpl cnentat ions, th is necessary type 

i n f o ma t i o : ■ wa s re co r A e d in 0. itself. 

In no re recent i n ;1 omenta u ions, the type info mat ion is 
car riei in the pointer to C_^_ This use of r i c h do into rs 
ref 1 ects two do vol opnents in 1 i s t-p recess ice inp 1 encntnt ion 



w= 



3.1 I nnod ia te va 1 no: 



If an atonic da tun c;>t\ be expressed In as few bits as 
di\ address, (1) then it is more efficient to copy such a 
datum than to handle it indirectly. But if "pointers" 

sonct ines conta i n i mined ia tc data i ns tea ■ of a id resses , then 



( 1 ) T ruth va 1 ues and sna 1 1 -napn i tude i n tore rs cxen:^ 1 i fy si 
data. 



po in te rs must al so conta in type Info mot ion to c'vmctcrizc 
the data they hold, 

3.2 V i rtua 1 none r i es 

Que ry i n; r type- i nf o mat ion is a cor^non 1 i st-n roc ess in°; 

ope ret ion. ( 1 ) In v i rtual -neno ry systens, v/ho re no; io n, 

re f e rences nay ho cos 1 1 y / it is oconon i ce 1 to pi ace 

typo- info mat ion i n the po into rs / so that rr.fr rences to the 
eel 1 s need not he node . 

k . An El omenta ry L ist-Trac i ng P roceduro 
^ . 1 Def in i t ions 

h ♦ 1 . 1 A wo rd is a quant i ty of neno ry suf f ic lent to hoi d 
an add ress . 

**r.l.2 A pointer is a two-v/ord object consisting of a 
t y p e - co d e an H an a d d re s s . 

U.1.3 A eel 1 is a set of one or iiorc contiguous v/or J s 



i n meno ry . 



he roqu \ renent of con t i ,;u i ty is innosod on 1 



that a single add ress son chow specif ins the whol e coll 



(1) E .;: . , thio functions aton , numbe rp , f i x p , etc, 
o r nantst in SLIP. 



i n 



LISP, 



■10- 



k . 1 J4 A wo rd in a. eel 1 C. nay br use i 

(a ) tone the r w i th the next wo rd in 0^ to 
conta in a po into r, o r 

(b) to contain the address of another cell Jj^ 
o r 

(c) to contain bits ( e , «: . > a floating-point 
nunbe r) wh ich a re ne i the r the type-cole of a 
pointer (as in (a)) nor the ad dress of another 
eel 1 D (as in (b)) . 



U.1.5 Two colls C. and C_I_ are of the sane type if an- 
o n 1 y i f 

(a) they a r^ of equal size and 

(b) for each word W in C^_ with co (respond In,: 
word Wl in C_|_, 

(i) if \L_ taken together with the 
next word in C^_ contains a pointer, then 
so do the co r res pond in;- wo rds in C ' . 

(ii) if U contains the address of 
another cell JJ^ then W_!_ contains the 
address of a cell b_|_ which is of the 
sane type as D_^ 

( i i i) if W contains bits which are 
neither the type-code of a pointer nor 



-li- 
the address of another cell 0^ than so 
does Wl. 

■ f 4.1.G Two pointers point to colls o f the sane typo if 
and only if they contain the sarin typo-code. 

h . 2 Tcnpl ates 

Cell -typo T can he descried with a tonpl ate of n + 1 
wo rd s , \ ■: h e re n is the n u n h. e r o f wo r\ s i n e a c K cell o f t y p e- 
T. 



(a ) Wo rd con ta ins n . 

(b) Fori ( i < n, 

(i) If words 1 an-\ 1+1 of each cell of type T 
contain a no inter, then word j_ of the template 
contains P^ a constant d iffc rent f ro: > any 
type-cod": . 



( i i) If word i of each ce' 



of 



c y p e i 



contains the a idrcss of a eel 1 of type Jl/ then 
v/o r i X of the tenalate contains t-e type-co l r of 
II. 

( I i i) If v/o rd J. of ^ r V cell of type X 



ih i r ■'■■ 



a m neither the 
pointer nor the a hiress of another 



-co. in of a 



'-.'O H J. of the template contains Z^ 
d Iff o rent from £ and from any twa-code 



OG i"; S t U t 



't . 3 The Key I do a 

I n o rde r to a I low a I i st-t rac in;; o roa ra m to t race: a 
list structure co; -to icier cells of type T^_ tho pro ; :rai mast, 
from the po inter to a coll of typo J^ be able to find the 
template for cells of type T. Tho simple, single, central 
i iea of th is pape r i s 

The typo-co ie for col Is of type T may he t- c 
a hi ress of tho tempi a to for cells of typo T^ 

h.h Tho Al ao r ithn 



A 1 i s t- t: rao in;; pror.edu rr is Mi s p ! ay od ho ro in a ! *:a star! 

f o ra of PL/1. As piveu, this procedure retraces shn^! 

subs t rue tu res, loops i raiof in i t e 1 y on men t rant s t rue tu res, 

and is hi ah 1 y racu rs i ve . 

1 is t_scan : p rocodu re ( typc__co Me, eel l__ah! ress , f ) ; 
Meclaro (typo_code, col l___a Hmss) add ress, 
f ex to rn a 1 ent ry ( a hi ress , a MM r~:ss ) ; 

/* Apply the fu net ion 'f ' to eve ry call of the list 
st ructu re whose root is a cell of type ! type__code ' at 
locot i o n 'cell __a d d ress 1 . * / 

dec la re eel !__wo ri( n) add ress based (eel l„a:d ress ) , 



-13- 

1 tempi ate base d ( typc_code) , 
2 n f ixed, 
2 to'iel ntc__wo rd(n) a I'! rnss, 

i local f ixod, 

( P, Z) external odd rss; 



i = i; 

do wh i 1 e ( i <_ n ) ; 

if tennl ato_wo H ( i ) = Z thon 
/* Co r respond inr; word 



in 



i t-oa t to rn wh i c! 



H 



1q ; 



the cell Is a 
not snoc i f y a 



1 ist-ch i 1 d of the cpI 1 . In ot'e r wo r Is, t-'-r 
co r re spend inr wo r ! of t'*o cell is i rr^l event 
to 1 i s t-t rac h\z. * I 

i = i+1 /* Skip past the irrelevant wo H */; 

else if tenpl atoj/o ret CI) = " then 

/ * Co r res pond inrr wo H in the cell is a 
t y p e - c o d c , ?nd the f o 1 1 o w i n ; : wo r d in the cell 
is an add r^ss. Toaethc r, these spec i fy a 

1 ist-ch ild of the eel 1 . */ 



oO , 



e n d ; 



cal 1 1 ist__scan(cel Ij./o rd ( i ) , 

eel l_wo rd( i + 1), f ); 
i = i + 2 ; 



el se 



/ * Co r re s po n d i n r; wo ri i r: t h e cell is the 
address of a list-child cell whose type is 
given by this word in the tonplnte.*/ 



end; 



do; 



end; 



cal 1 1 ist_scan( tenpl ate_wo r !( i ) , 

eel l_wo H( i ) , f ) ; 
i = i+1; 



call f ( type_eodr / eel l__ad -' rss); 
re tu rn; 



•lh- 



end 1 i s t_ scan; 

5 . Some hi a ho rat ions of t h c El orient a rv ProceHu re 

5.1 Immediate Dot a (cf. Section 3.1 above) 

As shown i n Sect ion h . h above, the cl emonta ry P rocedu re 
almost al lov;s tempi ates w ith n. = f ' • The on1 V necessa ry 
change is to nake the call of £ conditional upon n. > 0. 

For added efficiency, of course, the loop could he 
el oho rated so as to avo id spu rious sel f-cal 1 s fo r process in>^ 
of descendant po inters which contain immed iate lata in the 
place of addresses. 

5.2 Classes of Types 

Ce rta in ope rat ions at in.^her 1 eve! s of the systrn mpy 
involve classes of types. For example, numbers, arrays, ;jn ! 
var iabd cs a re all "a tons" to LISP. It may be useful to ad 1 
a wo rd of flar; hits to each tempi ate so Limit classes of 
types may be easily distinguished. 



5.3 Re-en t rant Lists and Sha red Suhst ruetu r: 



The el ementary p rocedu re will exe rt redundant of fo rt on 
shared substructure, and it '-/ill exert unbounde :\ effort: on 



-15- 

reent rant 1 i sts . Sonet imes these cases nay bo avo i ^Ic1 by 
us i tig s imp! if ?ed tempi ates; at other Limps, mark i ma will be 
necessa ry . 

5.3.1 SI: ip 1 if ie .! Temp 1 ates 

By the 'definition of roent rant implicit in Section ^.1 
above, many structures are reentrant even thoaeh t u ey v.'ou'bi 
not ordinarily be so dcscri ! e J . for example, consi 'er any 
structure in which no inters ar Hatched by u eck-po into rs , as 
in SLIP. Sue:: a structure is its own 1 i s t- ;: ran ich i 1 i, an-' 
reent rant f o r au rposes of the e 1 cacnt-.i ry p roar du re . 

This superficial raentrancy is not not ice i in 

traditional systems since hand- ta i 1 o red 1 ist-tracers kavn 
always been sens ibl c enough to fol low only one set of 
po inters. To as tab 1 isk this r-st r ict ion he m, tie 

back-po into r wo rds of the s\>d roo r iate tempi ales can be set 
to Z ( !, th is is not an address"), even t-ouah thn 

co r respond in- wo r-^ in the cells do r^a 1 1 y conta in 

add resses . 



5.3.2 Ma rk i nr; 

b'hen t rue reerit re.ncy i s nose iM e , L he 1 is t- 1 rac i nr 

oroco'lurp must ma rk traced lists so that thoy am not t racr- 



rain as their own 1 is t- ! osoerrkjnt s . 



a;; 

dos i rnbl o to 

subs t ructu ro . 



also 



avo i 



ra "km da at t rr.c in~ 



or 



■ a r a 



t nay happen t'at colls or certain 
typos arc never tho roots of rc-rn t rnnt or ska re d 
st ructu res . Cells of these: typos need novo r he 
ma rkcci . 

5.3.2.2 If tho list-tracer is fiakinp use of 
narking, it will interrogate a hit in the template 
to see if this eel 1 should ho na rked. 

5.3.2.3 if colls of this typo shouid be 
■narked, then the location of the nark must he 
detemi ncA. The 1 ocat ion nay ho set by convent i or 
( e m cr m , any cell vyh i ch is narko"! is narked in its 
f i rst i7 o H ) or by tho p rr sorter of a soec i a 1 cola 
(1 ike _P an i 1) in the co r resoon a ir a word of Ike 
ten.nl ate . 

If this cell is al ready na rke d, tkon the 1 ist-t race r 
retu rns. Otherw i sc, the 1 ist-t race r nark this eel 1 and 
traces its subs t ructu ro . 



-17- 

Ecc h use of a narking list-tracer nay need to be 
fol 1 owed by a list-trace to reset the na rks . Al to rnatol y, 
if a broad field is used for marking, then each trace can 
use a new b i t-pa tte rn ( say, con sec ut i ve i n te re rs ) as the 
nark. (1) 

5.3.3 Ref e rence Counts 

The: use of re fe rence counts for sto rape nan a tenant |l2J 
is fomally similar to the use of narking. In particular, 

the cons i do rat ions of pa ran raphs 5.3.2.1-3 a re al 1 
appl icable to reference counts. 

5 . h L inea r Lists 

L inear lists an: conuor: in 1 i s t-p races s in- 

appl icat ions . I n othe r .70 r Is, it is connon f o r each ce 1 1 of 
a ,j_;iven type to ut i 1 i ze a r iven wo r r .\ fo r the address of 
another cell of the sane type. To indicate the end of the 
list, a distinctive bit-pattern ( e . ;: . , all zero) is used. 



I t nay be econon ica 1 to use a b i t in the tenp 1 ate to 
indicate that the associated cells a re nenkc rs of linear 
lists. Then, the list-tracer can use a h ink-speed loop 
instead of a self -call for each cell of linear list. 



( 1 ) Th is techn i quo is due to Ma rt in R i cha r !s . 



■13- 



5 .5 Othe r Spec ial Cases 

In certain a^nl ica t i oris, the list-tracinc pro -ran ney 
need to take account of i d iosyncre t ic o rone rt ios of ce rta In 
cell -types. For oxsnpln, suonoso that a 1 ist-sc?.nn~ r is 

be inn used to scan d is en r bo d structu r^s (Section --.3,2 
above) in an algebraic inter;) rotor which- includes calls of 
type va riabl o. One of these cells should bo returned to f re e 
sto ra;-e onl y if 

(a) its reference count has oone to zero, on-,.! 

(b) there is no value associate 1 with this variable. 

Sone variables nay additionally be; specially protected f ron 
d isapp^a ranee . 

The interpreter nay have all of the variable cells 



to ^r\ I dent if ie r hash table. 



i S i : 



when a v a r i a !.: 1 e cell is t o b e re t ' i re o ! to f re o s t o t t 

hash- tab 1 c- cha i o nus I be no te'v^b 



The various actions of thus exoiplo rn isJ-L ell he 
t r I ' ee re 1 !;- y a hit in the- to in Into of cells of type 
va ri abl o ■ biffi ienco about eivi: - % this sort of 

appl icat ion-dependent information to the 1 is t-p rocess i ro< 
routines nay be offset by the arrunonts of Section 7 below. 



5 . kon-Recu rs i vo List 3cann inn 

In some onvironnonts, it v/ ill Ko ocononiccl to rewrite 
the list-scanner so as to avo i .: recursive cells. 

u . I Loca i Stack in;: 

if nonory usak] c as e stack is ave i 1 aki e, aec u 

recursive call of the list-scanner can V; replace ! with a 
"sushi" ope rat ion of tko no into r a rpument . Thcr; t ti o 

1 ist-scannor corio is all surroun^e -;i by a loop \ 
po inte rs f rom the stnch unt i 1 t N o stack is empty . 

5 . 2 The Deutsch-f cho r r-'. 'a 1 te Al <v- rit ! -n 



f a stack 



I : 



avai laMc, tk 



i i st- scan n in a 

technique of kcutsck, Schorr, an-! 'eaitc(l) may ke 

anp rop r iato. The Deutsck-3cko rr-\U' i to (i 3W) teokn kpje us^s 



the sea [ine 



scan. 



list itself for temporary storapa -lurn 



5.2.1 The Alpo ritkm 

Consider a list structure consist!;;: (in part) of 
prarnipareet cell fS^ a earent cell P^ ore! a chiM cell C_^_ 
scan cell jC^. the list-scanner nor Js 
(i) it is crcditci to them ir: [uj , 



To 



r>. kl7 



-2 0- 

( a ) the type of C^ and 

(h) the address of C^ an* 

( c ) an index v / 1 ■ I c h \ ' i 1 1 re n a o over the 



wo res 



of C. 



T h e DS'J list scanner also ronef nho rs 1: ! ^s~ datn for coll 



'/hon the DSW list-scanner returns to £ fro; 



it oust 



(a) discard its data concerning CL^ and 

(b) roplace its data concern in;; _C by its data 
conce m i n;; P^_ an' 1 

(c) somehow roplace its data concern in;:; £ by 
tbe co rrcspon'S inr data concornin.^ GLs. 

Those data concern inn 11 arc rot Moved f row a wo rd of 
eel 1 P^_ where they v/" re sto red when the 03V/ scanner was 
about to novo from £ down to C^ The word used for these 
data is simply that word of £ contain inr the address of C_^ 
Since the data conce mi nr; C a r^ kept alive within the DSl' 
p ror, ran du r i n;: ope ra t ions on C^ cor t i nuous sto reac of those 
data in £ is not essential. Of course, these -'eta must he 
resto red to £ upon retu rri f ran C_^_ bef o re they a re 
M d isca rded 1 ' as sunaestod just abov^ . 



,91- 



5.2.2 Applicability of the Aleorit-m 

The USW schonc nay require that a spore uorJ or two ho 
p resent in eve ry cell, Th is is so because al though th roc 



data (type, address, and 



ite rna 1 index ) conce m i n;i th 



grandparent cell must be temporarily sto rcA in the parent 
cell, only one datum (address) conce rnir;; the child cell nay 
be the re to be ove rw rittcn. At best, the ch i 1 d coll w i 1 1 
have been identified with two words (type and address), an! 
the grandparent's internal index w il 1 st il 1 be boneless. 

In practical cases, there ere frequently a few extra 
bits available in each cell. It m iqht be noted, mor-over, 
that the inte mal index may be rep rcsentnM e w i th as 1 itt 1 e 



as one bit; this was i t : 



inpl erientat ion . 



! 7.C 



in t [ e original VT\'. 



7 . On Sub rout ines a n d Techn ical Conmun i cat ion 

Most of the v a r io us list- o r a c e s s i r ■■ z t e c h n i q u e s 
described above have been implemented fo \ use in an 
algebraic: interpreter. The interpreter uses cells of seven 
d if re rent si zes an^l about fifty d if f e rent types . Th is 
paper, instead of be in;- -wholly devoted to discussion of the 
underlying techniques, mifdit have note concerned itself with 



-2 2- 

t ! ■ ■ c no '1 u 1 a r i ze tion, col 1 irvi-sonu o nccs, e n 
Hetnils. 



o t h e r 



1 3c!;- ! x); 



This toe h n i e u o - o r in n t e d 'inscription is the re s u 1 t o f 
view nbout the stnto of p ro- rente i rip . A fov/ ynpr-; a; 



1 i s t-p rocoss i up was en e rcane ar 



difficult } u.:f, i'^oss . Us- rs 



wo re not: into rested in the into rnn 1 tcc'-r Jeues, nny no r~ 
then, e fov.' no re years epo, t u oy h<ed be on interests-: in the 



i nte mo 1 techn k;uos 



rout in 3 . 



of f 1 oot ir:~-po in t inte re rot ive 



Todey, the teckn ioues once use.! oel y e i Lh in 

speciol ists 1 f 1 or- 1 i np-po in t routines e. re coir-.! in-1 ins by 
everyone. S inn lo r'i y, 1 is t-p roc ess in- codn is today no re 

often ta i 1 o red then boupht off the reck. 



i n e 



1 i s t i op- lovers, no doubt , nou Id h r in touch w i th 



1: h e aut: ho r no nn 1 1 o r w hat 



M , 



-'; . Ac know 1 odennonts 

The author is Indent e:- to P rof . J . no: 
encou reeenent, to C. p ev: itt end P. Sussien for t u n i r 
consents on en eerly ..!r.?ft, err' to Prof. Arthur Evens, Jr., 
f o r b r ins Inp the wo rk of 3 . Me r: 
Richards to the author's attention* 



du>l 1 [:;] en 



'\3 rt in 



-23- 



1. Abrahams, Paul 11. et a_U "The LISP 2 P roz rammi n;; 
L a n ft u a p o and S y s t c n , " AN PS Proceed imrs, X X IX (Fall, 1 P U 5 ) , 
p p . 6 '5 1 - u 7 b . 

2 . A n o n ynous. PL/1 Reference Manual (IPX Co r po r a L i o n , 
1 96 3 ) . 

3. Boh row, Daniel G., and Murphy, Daniel L. "Structure of a 
LISP System Us in-; Two- Level Storage," CACM, X, 3, (Parch, 
1PG7), pn. 155-15']. 

it. Fonichel, Kobe rL P., and Yocholso:i, J c: roue? C. "A LIS,' 
Ga rba;;e Co 1 1 ecto r f o r V i rtua 1 -Menu ry Compute r Systems , " 
CACM, XII, 11 (November, 1 So SO , PP. S11-G12. 

5. Hawkinson, L. "LISP 2 Internal Storage Conventions." 
System Development Corporation Tech Memo TM.-3^ 17/55u/ 30 
( S a n ta Mo n i ca , 1 % 7 ) . 

6. Knuth, Donald E. Fundamental Al ~o r ithms (Peadin-, 
Massachusetts: Add Ison-Wes 1 ey , IPCS). 



7. Lang, Charles A. "SAL-Systrns Assembly Lanftua;-c 
Proceedings, XXXIV (Soring, 1%H), pry, 5 '* "3 - 5 f» 7 . 



1 1 »ri nr 



-2b- 

8. Marshall, S. "An Al to! GS Carboy Collector." i'iewit 
Coriputat ior: Centor Technical Meno raivlun Tf 01 1 (Hanover, Pew 
Mampsh i re : Pa rtnoutb Co 1 1 opr , 1 99 9) . 



9. McCarthy, John. "Recursive Functions of Symbolic 

iy Mach ine - 



and Their Conputat ion fw M-ir'« ir.r. - l." C/\rP 



Lxp re ss i ons 

III, 't (April, 19G0), pp. 10>t-iG3. 



10, 



et al . LISP 1.5 P roy;rainno r' s Manual ( Can J; r i :.!;:;c 



MIDPress, 1905). 

11. Ross, D.T. AED-0 Pro;: ramming Manual (Mectoc, rnphor!, 
1 96 k ) . 

12. Woizcnbaun, J. "Symetric List Processor," 9ACM, VI, 9 
(September, 19G3), pp. 52h-:U\h. 



13 



II n 



Recovery of Reentrant List Structures ii 



LIP," CACM, XII, 7 (July, 199°), no. 370-372. 



R ichn ris to t!'<n author's at tent: tori